/*
 * A binary search tree implementation.
 * Copyright 2009 sevenever <sevenever@gmail.com>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <stdlib.h>
#include "bst.h"

typedef struct __node
{
  void * data;
  struct __node * left;
  struct __node * right;
}
  node, * pnode;

typedef struct __bst
{
  pnode root;
  bst_compare_func compare;
}
  bst;


//construct a new node
static pnode new_node(void * data)
{
  pnode node = (pnode)malloc(sizeof(node));
  if(!node)
    {
      return NULL;
    }
  node->data = data;
  node->left = NULL;
  node->right = NULL;
  return node;
}

//a new tree
pbst bst_new(bst_compare_func compare)
{
  pbst tree = (pbst)malloc(sizeof(bst));
  if(!tree)
    {
      return NULL;
    }
  tree->root = NULL;
  tree->compare = compare;
  return tree;
}

static void dispose_subtree(pnode node, bst_free_func freefunc)
{
  if(!node)
    {
      return;
    }
  dispose_subtree(node->left, freefunc);
  dispose_subtree(node->right, freefunc);
  if(freefunc != NULL) freefunc(node->data);
  free(node);
}

//delete a tree
void bst_dispose(pbst tree, bst_free_func freefunc)
{
  //delete all subtree
  dispose_subtree(tree->root, freefunc);

  //free
  free(tree);
}

//insert a data into tree
//return tree pointer after insert. NULL if error
pbst bst_insert(pbst tree, void * data)
{
  pnode node;
  //compare result
  int c;
  
  if(!tree->root)
    {
      //tree is empty
      //new node
      tree->root = new_node(data);
      return tree;
    }
  else
    {
      //tree has some node
      node = tree->root;
      
      while(1)
	{
	  c = tree->compare(data, node->data);
	  //found the same data, just return
	  if(c == 0) return tree;
	  //smaller than left and left is NULL, insert here
	  if(!(node->left) && c< 0){
	    node->left=new_node(data); return tree;
	  }
	  
	  //larger than right and right is NULL, insert here
	  if(!(node->right) && c> 0){
	    node->right=new_node(data);
	    return tree;
	  }
	  
	  //go to sub tree
	  node = c<0 ? node->left : node->right;
	}
    }
}

//delete a node from tree
void bst_delete(pbst tree, void * data)
{
  pnode node;
  pnode * tonull;
  //compare result
  int c;
  
  if(!(tree->root))
    {
      //tree is empty, just return
      return;
    }
  else
    {
      //tree has some node
      node = tree->root;
      tonull = &(tree->root);
      
      while(1)
	{
	  c = tree->compare(data, node->data);
	  //found the same data, just return
	  if(c == 0){
	    *tonull=NULL;
	    return;
	  }
	  
	  //smaller than left and left is NULL, just not found
	  //larger than right and right is NULL, just not found
	  if( ( !(node->left) && c<0 )
	     || ( !(node->right) && c>0 ) ){
	    *tonull=NULL;
	    return;
	  }
	  
	  //go to sub tree
	  if(c<0){
	    tonull = &(node->left);
	    node = node->left;
	  }else{
	    tonull = &(node->right);
	    node = node->right;
	  }
	}
    }
}

//search in a tree, return NULL if not found
void * bst_search(pbst tree, void * data)
{
  pnode node = tree->root;
  //compare result
  int c;
  
  while(node)
    {
      c = tree->compare(data, node->data);
      if(c==0)return node->data;
      node = c<0 ? node->left : node->right;
    }
  
  return NULL;
  
}

static void walk_subtree(pnode node, bst_act_func action, int level)
{
  if(node->left == NULL && node->right == NULL)
    {
      action(node->data, leaf, level);
    }
  else
    {
      action(node->data, preorder, level);
      if(node->left != NULL)
	walk_subtree(node->left, action, level+1);
      action(node->data, postorder, level);
      if(node->right != NULL)
	walk_subtree(node->right, action, level+1);
      action(node->data, endorder, level);
    }
}
  
//walk through the tree
void bst_walk(pbst tree, bst_act_func action)
{
  walk_subtree(tree->root, action, 1);
}

